home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / dp_hashi.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  4.3 KB  |  218 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  dp_hashing.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17.  
  18.  
  19. //------------------------------------------------------------------------------
  20. // Dynamic Perfect Hashing
  21. //
  22. // Michael Wenzel          ( 1989/90 )
  23. //------------------------------------------------------------------------------
  24.  
  25.  
  26. #ifndef DPHASHINGH
  27. #define DPHASHINGH
  28.  
  29. #include <LEDA/basic.h>
  30.  
  31.  
  32. // ---------------------------------------------------------------
  33. // declarations
  34. // ---------------------------------------------------------------
  35.  
  36.  
  37. class headertable;
  38. class subtable;
  39. class dphash;
  40.  
  41. typedef headertable* htp;
  42. typedef subtable* stp;
  43.  
  44. #define EMPTY (ent(2147483648))
  45. #define maxuni 2147483647
  46.                                 // #define maxprim 2147483659
  47.                 // aber kleiner wegen random-Funktion
  48. #define maxprim 2147483647
  49. #define wursechs 2.44948974278
  50.  
  51. // --------------------------------------------------------------
  52. // class declarations
  53. // --------------------------------------------------------------
  54.  
  55. // --------------------------------------------------------------
  56. // class headertable
  57. //
  58. // Items werden auf Headertables gehasht,
  59. // die sie dann injektiv auf Subtables verteilen
  60.  
  61. class headertable {
  62.  
  63.   unsigned kj;                     // Multiplikator
  64.   int wj;                          // Anzahl Elemente in Tafel
  65.   int mj;                          // max. Anzahl Elemente
  66.   stp tj;                          // Startpunkt der Subtables
  67.  
  68.   friend class b_dict;
  69.   friend class dphash;
  70.   friend class subtable;
  71.  
  72.   stp lookup(ent );
  73.  
  74.   bool insert(ent ,ent ,stp& ,int& ,bool& ,stp ,stp );
  75.   int dinsert(ent ,ent ,stp ,stp& ,stp& );
  76.  
  77.   bool del(ent ,stp ,stp ); 
  78.   int give_elements(stp& ,stp ,stp );  
  79.  
  80.  
  81.   headertable()
  82.     { 
  83.       kj = wj = mj=0; 
  84.       tj=0;   
  85.      }
  86.  
  87.   OPERATOR_NEW(4);
  88.   OPERATOR_DEL(4);
  89.  
  90. };
  91.  
  92. // --------------------------------------------------------------
  93. // class subtable
  94. //
  95. // Jedes Subtableelement ist leer,
  96. // oder von der Headertable wird genau ein Element    
  97. // auf eine Position gehasht
  98.  
  99. class subtable {
  100.  
  101.   ent ke;
  102.   ent inf;
  103.  
  104.   friend class b_dict;
  105.   friend class dphash;
  106.   friend class headertable;
  107.  
  108.   void set_s(ent a,ent b)
  109.     {
  110.        ke=a; inf=b; }
  111.  
  112.   void clear()
  113.     { 
  114.        ke=EMPTY; inf=0; }
  115.  
  116.   subtable()
  117.     {  
  118.        ke=EMPTY; inf=0; }
  119.  
  120.   subtable(ent a ,ent b )
  121.     {  
  122.        ke=a; inf=b; }
  123.  
  124.   subtable(subtable& s)
  125.     {  
  126.        ke=s.ke;
  127.        inf=s.inf; }
  128.  
  129.    subtable& operator=(subtable& s)
  130.     {
  131.        ke=s.ke;
  132.        inf=s.inf;
  133.        return *this; }
  134.  
  135.  OPERATOR_NEW(2);
  136.  OPERATOR_DEL(2);
  137.  
  138.   public:
  139.  
  140.   ent key() { return ke; }
  141.  
  142.   ent info() { return inf; }
  143.  
  144. };
  145.  
  146. // ------------------------------------------------------------------
  147. // class dphash
  148. //
  149. // alle Informationen fuer das Dictionary
  150. // Elemente werden auf Headertables gehasht, 
  151. // die dann die Elemente weitergeben
  152. // Der Platzverbrauch der Headertables wird kontrolliert
  153.  
  154.  
  155. class dphash {
  156.  
  157.   htp* htablep;      // Feld von Zeigern auf Headertables
  158.              // leere Headertables werden nicht angelegt
  159.  
  160.   unsigned k;        // Verteilungsfunktion (k*x)%p%sM
  161.  
  162.   int n;             // Anzahl Elemente im Dictionary
  163.  
  164.   int M;             // Anzahl Elemente, die momentan bzgl.
  165.              // Platzverbrauch mit Wahrscheinlichkeit >= 0.5
  166.              // abgespeichert werden koennen ( ohne Rehash )
  167.  
  168.   int sM;            // Anzahl Headertables
  169.  
  170.   int bed;           // Kontrolle des Platzverbrauchs
  171.  
  172.   stp anf,wo,ende;   // zur Speicherverwaltung beim Rehash
  173.  
  174.  
  175.  
  176.   stp  rehash_all(ent ,ent );
  177.  
  178.  
  179.   virtual void clear_key(ent&) {}
  180.   virtual void clear_inf(ent&) {}
  181.  
  182.   virtual void copy_key(ent&)  {}
  183.   virtual void copy_inf(ent&)  {}
  184.  
  185. public:
  186.  
  187.   ent  key(stp it)
  188.     { return ( it ) ? it->key() : 0 ; }
  189.  
  190.   ent& info(stp it)
  191.     { if (!it) error_handler(1,"dp_item gleich nil");
  192.       return it->inf; }
  193.  
  194.   stp  insert(ent ,ent );
  195.   void del(ent );
  196.  
  197.   int  member(ent );
  198.   stp  lookup(ent );
  199.  
  200.   stp  change_inf(ent ,ent );
  201.  
  202.   int  size()
  203.     { return n; }
  204.  
  205.   void clear();
  206.  
  207.  
  208.   dphash();
  209.   dphash(int ,ent* ,ent* );
  210.   ~dphash();
  211.  
  212.  
  213.   friend class b_dict;
  214.  
  215. };
  216.  
  217. #endif DPHASHINGH
  218.